package com.terrier.math.bigInteger
{
    use namespace bi_internal;

    internal class BarrettReduction implements IReduction
    {
        private var m:BigInteger;
        private var r2:BigInteger;
        private var q3:BigInteger;
        private var mu:BigInteger;

        public function BarrettReduction(m:BigInteger)
        {
            // setup Barrett
            r2 = new BigInteger;
            q3 = new BigInteger;
            BigInteger.ONE.dlShiftTo(2 * m.t, r2);
            mu = r2.divide(m);
            this.m = m;
        }

        public function revert(x:BigInteger):BigInteger
        {
            return x;
        }

        /**
         *
         * @param x
         * @param y
         * @param r = x*y mod m; x != r
         *
         */
        public function mulTo(x:BigInteger, y:BigInteger, r:BigInteger):void
        {
            x.multiplyTo(y, r);
            reduce(r);
        }

        /**
         *
         * @param x
         * @param r = x^2 mod m; x != r
         *
         */
        public function sqrTo(x:BigInteger, r:BigInteger):void
        {
            x.squareTo(r);
            reduce(r);
        }

        public function convert(x:BigInteger):BigInteger
        {
            if (x.s < 0 || x.t > 2 * m.t)
            {
                return x.mod(m);
            }
            else if (x.compareTo(m) < 0)
            {
                return x;
            }
            else
            {
                var r:BigInteger = new BigInteger;
                x.copyTo(r);
                reduce(r);
                return r;
            }
        }

        /**
         *
         * @param x = x mod m (HAC 14.42)
         *
         */
        public function reduce(lx:BigInteger):void
        {
            var x:BigInteger = lx as BigInteger;
            x.drShiftTo(m.t - 1, r2);
            if (x.t > m.t + 1)
            {
                x.t = m.t + 1;
                x.clamp();
            }
            mu.multiplyUpperTo(r2, m.t + 1, q3);
            m.multiplyLowerTo(q3, m.t + 1, r2);
            while (x.compareTo(r2) < 0)
            {
                x.dAddOffset(1, m.t + 1);
            }
            x.subTo(r2, x);
            while (x.compareTo(m) >= 0)
            {
                x.subTo(m, x);
            }
        }

    }
}